package com.zxy.leetcode.lcof;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
 *
 * 数组中出现次数超过一半的数字
 * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 *
 * 解法：排序、Map、分治、摩尔、位运算
 *
 * https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/mian-shi-ti-39-shu-zu-zhong-chu-xian-ci-shu-chao-3/
 * 摩尔投票法
 * 投票法简单来说就是不同则抵消，占半数以上的数字必然留到最后。
 * 设输入数组 nums 的众数为 xx ，数组长度为 nn 。
 * 推论一： 若记 众数 的票数为 +1 ，非众数 的票数为 -1 ，
 *  则一定有所有数字的 票数和 > 0 。
 * 推论二： 若数组的前 aa 个数字的 票数和 = 0 ，
 *  则 数组剩余 (n-a) 个数字的 票数和一定仍 >0 ，
 *  即后 (n-a) 个数字的 众数仍为 xx 。
 */
public class Test39 {

    public static void main(String[] args) {
        Test39 test = new Test39();
        int[] nums = {1, 2, 3, 2, 2, 2, 5, 4, 2};
        System.out.println(test.majorityElement(nums));
    }

    // 用HashMap实现
    public int majorityElement(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int halfCount = nums.length / 2 + 1;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i=0; i<nums.length; i++) {
            Integer count = map.get(nums[i]);
            if (count == null) {
                map.put(nums[i], 1);
            }else if (count + 1 >= halfCount) {
                return nums[i];
            }else {
                map.put(nums[i], count + 1);
            }
        }
        return 0;
    }

}
